package com.study.lintcode.my.code_20;

/**********************************************************************   
 * &lt;p&gt;文件名：Example_13.java &lt;/p&gt;
 * &lt;p&gt;文件描述：(https://www.lintcode.com/problem/implement-strstr/description)
 * @project_name：LintCode
 * @author zengshunyao
 * @create 2019/1/6 0:33 
 * @history
 * @department：政务事业部
 * Copyright ChengDu Funi Cloud Code Technology Development CO.,LTD 2014 
 *                    All Rights Reserved.
 */
public class Example_13 {
    /**
     * @param source:
     * @param target:
     * @return: return the index
     */
    public int strStr(String source, String target) {
        char[] schars = source.toCharArray();
        char[] tchars = target.toCharArray();
        int slen = source.length();
        int tlen = target.length();
        int i, j;
        i = j = 0;
        while (i < slen && j < tlen) {
            if (schars[i] == tchars[j]) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }
        if (j == tlen) {
            return i - j;
        }
        return -1;
    }

    //考察目标字符串ptr：
    //ababaca
    //这里我们要计算一个长度为m的转移函数next。
    //
    //next数组的含义就是一个固定字符串的最长前缀和最长后缀相同的长度。
    //
    //比如：abcjkdabc，那么这个数组的最长前缀和最长后缀相同必然是abc。
    //cbcbc，最长前缀和最长后缀相同是cbc。
    //abcbc，最长前缀和最长后缀相同是不存在的。
    //
    //**注意最长前缀：是说以第一个字符开始，但是不包含最后一个字符。
    //比如aaaa相同的最长前缀和最长后缀是aaa。**
    //对于目标字符串ptr，ababaca，长度是7，所以next[0]，next[1]，next[2]，next[3]，next[4]，next[5]，next[6]分别计算的是
    //a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀的长度。
    // 由于a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀是“”，“”，“a”，“ab”，“aba”，“”，“a”,
    // 所以next数组的值是[-1,-1,0,1,2,-1,0]，这里-1表示不存在，0表示存在长度为1，2表示存在长度为3。这是为了和代码相对应。
    //a          “”              next[0]=-1
    //ab         “”              next[1]=-1
    //aba        “a”             next[2]=0
    //abab       “ab”            next[3]=1
    //ababa      “aba”           next[4]=2
    //ababac     “”              next[5]=-1
    //ababaca    “a”             next[6]=0
    //未完待续   哦kmp
    /**
     * @param source:
     * @param target:
     * @return: return the index
     */
    public int KmpSearch(String source, String target) {
        char[] schars = source.toCharArray();
        char[] tchars = target.toCharArray();
        int slen = source.length();
        int tlen = target.length();
        int i, j;
        i = j = 0;
        while (i < slen && j < tlen) {
            //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
            if (j == -1 || schars[i] == tchars[j]) {
                i++;
                j++;
            } else {
                //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
                //next[j]即为j所对应的next值
//                j = next[j];
            }
        }
        if (j == tlen) {
            return i - j;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Example_13().strStr("source", "target"));
    }
}
